package com.learn.algorithm;

import java.util.Arrays;

/**
 * 归并排序
 * 空间复杂度：如果长度为N,那么折半的层数就是LogN
 * 时间复杂度：每一层的运算量乘以层级数即0(NlogN)
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] array = {5,8,6,3,9,2,1,7,4};
        mergeSort( array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }

    static public void mergeSort(int[] array, int start, int end ) {
        if (start < end ) {
            //折半成两个小集合，分别经i下那个递归
            int mid = (start+end) / 2;
            mergeSort(array,start,mid);
            mergeSort(array,mid+1, end);
            //把两个有序小集合，归并成一个大集合
            merge(array,start,mid,end);

        }
    }

    static private void merge(int[] array, int start, int mid, int end) {
        int[] tempArray = new int[end-start+1];
        int p1=start, p2=mid+1,p=0;
        //比较两个小集合元素，依次放入大集合
        while(p1<=mid && p2<=end) {
            if(array[p1] <= array[p2]) {
                tempArray[p++] = array[p1++];
            } else {
                tempArray[p++] = array[p2++];
            }
        }
        //检查左侧小集合还有剩余，依次放入大集合尾部
        while (p1<=mid) {
            tempArray[p++] = array[p1++];
        }
        //检查右侧侧小集合还有剩余，依次放入大集合尾部
        while (p2<=end) {
            tempArray[p++] = array[p2++];
        }
        //把大集合的元素复制回原数组
        for(int i=0;i<tempArray.length;i++){
            array[i+start] = tempArray[i];
        }
    }
}
